package q1636_frequencySort;

import java.util.*;

public class Solution {
    /*
    将数组按照每个值出现的频率 升序 排序。如果有多个值的频率相同，
    则按照数值本身将它们 降序 排序。
    按照数据范围nums[i]只能为-100 至 100
    所以直接用二维数组模拟hash表 其中map中分别存储 数字 ： 频率
    然后用arrays的sort排序后输出
    但是如果范围很大，则还是使用map比较好
     */
    public int[] frequencySort(int[] nums) {
        int[][] map = new int[201][2];
        for (int i = -100; i <= 100; ++i) {
            map[i + 100][0] = i;
        }
        for (int i = 0; i < nums.length; ++i) {
            map[nums[i] + 100][1]++;
        }
        Arrays.sort(map, (a, b) -> {
            if (a[1] == b[1]) return b[0] - a[0];
            return a[1] - b[1];
        });
        int idx = 0;
        for (int i = 0; i <= 200; ++i) {
            for (int j = 0; j < map[i][1]; ++j) {
                nums[idx++] = map[i][0];
            }
        }
        return nums;

//        // * 使用Map的方法 则需要使用Collection来排序
//        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
//        for (int num : nums) {
//            cnt.put(num, cnt.getOrDefault(num, 0) + 1);
//        }
//        List<Integer> list = new ArrayList<Integer>();
//        for (int num : nums) {
//            list.add(num);
//        }
//        Collections.sort(list, (a, b) -> {
//            int cnt1 = cnt.get(a), cnt2 = cnt.get(b);
//            return cnt1 != cnt2 ? cnt1 - cnt2 : b - a;
//        });
//        int length = nums.length;
//        for (int i = 0; i < length; i++) {
//            nums[i] = list.get(i);
//        }
//        return nums;

    }
}
